home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / AVL_TREE.H < prev    next >
C/C++ Source or Header  |  1992-08-20  |  5KB  |  129 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 06/28/89 -- Initial design and implementation
  13. // Updated: MBN 08/20/89 -- Updated template usage to reflect new syntax
  14. // Updated: MBN 09/19/89 -- Added conditional exception handling
  15. // Updated: DKM 11/05/89 -- Replaced re-balance after exceeding goal height
  16. //                          with true AVL rotation alorythm.
  17. // Updated: LGO 12/04/89 -- operator<< not inline
  18. // Updated: LGO 12/04/89 -- balance not inline
  19. // Updated: MJF 06/30/90 -- Added base class name to constructor initializer
  20. // Updated: VDN 02/21/92 -- New lite version
  21. // Updated: JAM 08/19/92 -- modernized template syntax, remove macro hacks
  22. // Updated: JAM 08/19/92 -- made *_state typedef a nested typedef "IterState"
  23. //                          as per new Iterator convention
  24. //
  25. // The AVL_Tree<Type> class implements height-balanced, dynamic,  binary trees.
  26. // The  AVL_Tree<Type> class is  publicly derived   from  the Binary_Tree<Type>
  27. // class and  both  are parameterized  over some type   Type. An AVL  tree is a
  28. // compromise  between the  expense  of a  fully balanced binary  tree and  the
  29. // desire for efficient search times for both average and worst case scenarios.
  30. // As a result, an AVL tree  maintains a  binary tree that  is height-balanced,
  31. // insuring that the minimum and maximum depth  of any path  through the binary
  32. // tree is within some specified range.
  33. //
  34. // The  AVL_Tree<Type>  class has  no private  data slots   and only two public
  35. // constructors.  The first constructor  takes an optional argument that allows
  36. // the user  to  specify  the height-balance limit  (the   default is  two).  A
  37. // height-balance  value   of  zero indicates    that  the  tree should  remain
  38. // completely balanced.   The second  constructor  takes a reference to another
  39. // AVL_Tree<Type> and duplicates its size and values.
  40. //
  41. // The  AVL_Tree<Type>  class   inherits  all its   methods  publicly from  the
  42. // Binary_Tree<Type> class. The only methods that are overloaded are those that
  43. // affect  the structure of  the tree, thus  potentially requiring  one or more
  44. // subtrees to be shaken and restructured.
  45. //
  46.  
  47. #ifndef AVL_TREEH                // If no definition for class
  48. #define AVL_TREEH
  49.  
  50. #ifndef BINARY_TREEH                // If no definition for class
  51. #include <cool/Binary_Tree.h>            // include definition file
  52. #endif
  53.  
  54. template <class Type>
  55. class CoolAVL_Tree : public CoolBinary_Tree<Type> {
  56.   
  57. public:
  58.   typedef CoolBT_State IterState;
  59.  
  60.   /*inline##*/ CoolAVL_Tree() {};            // Simple constructor
  61.   CoolAVL_Tree(const CoolAVL_Tree<Type>&);    // Copy constructor
  62.   CoolAVL_Tree(const CoolBinary_Tree<Type>&);    // Convert BT into AVL
  63.   ~CoolAVL_Tree();                // Destructor
  64.  
  65.   inline Boolean put (const Type&);        // Add an item to tree
  66.   inline Boolean remove (const Type&);        // Remove item from tree
  67.   inline Boolean remove ();            // Remove item current position
  68.   void balance ();                // Special balance for AVL
  69.   inline CoolAVL_Tree<Type>& operator= (CoolAVL_Tree<Type>&);  // Assignment overloaded
  70.   inline CoolAVL_Tree<Type>& operator= (CoolBinary_Tree<Type>&);//Assignment overloaded
  71.   friend ostream& operator<< (ostream&, const CoolAVL_Tree<Type>&);
  72.   /*inline##*/ friend ostream& operator<< (ostream&, const CoolAVL_Tree<Type>*);
  73. };
  74.  
  75.  
  76. // put -- Add a value to the AVL tree if it is not already there and balance
  77. //        tree if necessary
  78. // Input: Reference to value to add to tree
  79. // Output: TRUE if item added, FALSE otherwise
  80.  
  81. template <class Type> 
  82. inline Boolean CoolAVL_Tree<Type>::put (const Type& value) {
  83.   return (CoolBinary_Tree<Type>::put_internal (value, TRUE)); 
  84. }
  85.  
  86.  
  87. // remove -- Remove a value from the AVL tree. Deletion of a node and balance
  88. //           tree if necessary
  89. // Input:    Reference to value to remove
  90. // Output:   TRUE if item removed, FALSE otherwise
  91.  
  92. template <class Type> 
  93. inline Boolean CoolAVL_Tree<Type>::remove (const Type& value) {
  94.   return (CoolBinary_Tree<Type>::remove_internal (value, TRUE)) ;
  95. }
  96.  
  97.  
  98. // remove -- Remove node at current position in the tree and balance tree
  99. // Input:    None
  100. // Output:   Value of node removed from tree
  101.  
  102. template <class Type> 
  103. inline Boolean CoolAVL_Tree<Type>::remove () {
  104.   return (CoolBinary_Tree<Type>::remove_internal(this->value(),TRUE));
  105. }
  106.  
  107.  
  108. template <class Type> 
  109. inline CoolAVL_Tree<Type>& CoolAVL_Tree<Type>::operator= (CoolAVL_Tree<Type>& av) {
  110.   CoolBinary_Tree<Type>::operator= (av);    // Create the new Tree
  111.   return *this;                    // Return tree reference
  112. }
  113.  
  114. template <class Type>
  115. inline CoolAVL_Tree<Type>& CoolAVL_Tree<Type>::operator= (CoolBinary_Tree<Type>& bt) {
  116.   CoolBinary_Tree<Type>::operator= (bt);    // Create the new Tree
  117.   this->balance();                // Do an AVL balance
  118.   return *this;                    // Return tree reference
  119. }
  120.  
  121.  
  122.  
  123. template<class Type>
  124. inline ostream& operator<< (ostream& os, const CoolAVL_Tree<Type>* av) {
  125.   return operator<< (os, *av);
  126. }
  127.  
  128. #endif                        // End AVL_TREEH #if
  129.